package pers.qianyu.month_202102.date_20210207;

import org.junit.*;

import java.util.*;

/**
 * 907. 子数组的最小值之和
 * https://leetcode-cn.com/problems/sum-of-subarray-minimums/
 *
 * @author mizzle rain
 * @date 2021-02-07 17:20
 */
public class SumSubarrayMins {
    public int sumSubarrayMins(int[] nums) {
        int len = nums.length;
        int mod = 1000_000_007;
        Deque<Integer> st = new ArrayDeque<>();
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < nums.length; i++) {
            // 假设了每个子数组如果最小值出现多次，那么只取第一次出现的最小值。所以左边取小于，右边取小于等于。
            while (!st.isEmpty() && nums[st.getLast()] > nums[i]) st.pollLast();
            left[i] = st.isEmpty() ? -1 : st.getLast();
            st.addLast(i);
        }
        st.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!st.isEmpty() && nums[st.getLast()] >= nums[i]) st.pollLast();
            right[i] = st.isEmpty() ? len : st.getLast();
            st.addLast(i);
        }
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum % mod + (long) nums[i] * (i - left[i]) * (right[i] - i) % mod;
        }
        return (int) sum;
    }

    @Test
    public void test1() {
        int result = new SumSubarrayMins().sumSubarrayMins(new int[]{3, 1, 2, 4});
        System.out.println("result = " + result);
        Assert.assertEquals(17, result);
    }

    @Test
    public void test2() {
        int result = new SumSubarrayMins().sumSubarrayMins(new int[]{11, 81, 94, 43, 3});
        System.out.println("result = " + result);
        Assert.assertEquals(444, result);
    }

    @Test
    public void test3() {
        int result = new SumSubarrayMins().sumSubarrayMins(new int[]{71, 55, 82, 55});
        System.out.println("result = " + result);
        Assert.assertEquals(593, result);
    }
}
